package graph

func allPathsSourceTarget(graph [][]int) (res [][]int) {
	var path []int
	var traverse func(s int, path []int)
	traverse = func(s int, path []int) {
		path = append(path, s)

		if s == len(graph)-1 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
			return
		}

		for _, vertex := range graph[s] {
			traverse(vertex, path)
		}

		path = path[:len(path)-1]
	}

	traverse(0, path)

	return
}
